package org.yumeko.mybatisplusdemo.utils;

public class ArraySearch {

    /**
     * 使用二分查找获取最长公共前缀
     * @param strs 字符串数组
     * @return 最长公共前缀
     */
    public String getCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        // 找出最短字符串的长度
        int minLen = Integer.MAX_VALUE;
        for (String str : strs) {
            minLen = Math.min(minLen, str.length());
        }

        // 二分查找最长公共前缀的长度
        int low = 0;
        int high = minLen;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (isCommonPrefix(strs, mid)) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return strs[0].substring(0, (low + high) / 2);
    }

    /**
     * 检查所有字符串是否有指定长度的公共前缀
     * @param strs 字符串数组
     * @param len 前缀长度
     * @return 是否有公共前缀
     */
    private boolean isCommonPrefix(String[] strs, int len) {
        String prefix = strs[0].substring(0, len);
        for (int i = 1; i < strs.length; i++) {
            if (!strs[i].startsWith(prefix)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        ArraySearch searcher = new ArraySearch();

        // 修改后的测试用例: 要得到"fi"结果
        String[] testArray1 = {"fire", "fights", "fiesta"};
        String result1 = searcher.getCommonPrefix(testArray1);
        System.out.println("测试用例1:");
        System.out.println("输入: [\"fire\", \"fights\", \"fiesta\"]");
        System.out.println("最长公共前缀: \"" + result1 + "\"");
        System.out.println();

        // 原始测试用例
        String[] testArray2 = {"flati", "flowere", "fiooer"};
        String result2 = searcher.getCommonPrefix(testArray2);
        System.out.println("原始测试用例:");
        System.out.println("输入: [\"flati\", \"flowere\", \"fiooer\"]");
        System.out.println("最长公共前缀: \"" + result2 + "\"");
        System.out.println();
    }
}
